<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 时间O(n)
        // 空间O(1)
        // 使用卡塔兰数的公式
        // Cn = Cn-1 * 2 * (2 * i + 1) / (i + 2)
        var numTrees = function (n) {
            let c = 1
            for (let i = 0; i < n; i++) {
                c = c * 2 * (2 * i + 2) / (i + 1)
            }
            return c
        };
        console.log(numTrees(3));
    </script>
</body>

</html>